"""
679. 24 点游戏
困难
相关标签
premium lock icon
相关企业
给定一个长度为4的整数数组 cards 。你有 4 张卡片，每张卡片上都包含一个范围在 [1,9] 的数字。您应该使用运算符 ['+', '-', '*', '/'] 和括号 '(' 和 ')' 将这些卡片上的数字排列成数学表达式，以获得值24。

你须遵守以下规则:

除法运算符 '/' 表示实数除法，而不是整数除法。
例如， 4 /(1 - 2 / 3)= 4 /(1 / 3)= 12 。
每个运算都在两个数字之间。特别是，不能使用 “-” 作为一元运算符。
例如，如果 cards =[1,1,1,1] ，则表达式 “-1 -1 -1 -1” 是 不允许 的。
你不能把数字串在一起
例如，如果 cards =[1,2,1,2] ，则表达式 “12 + 12” 无效。
如果可以得到这样的表达式，其计算结果为 24 ，则返回 true ，否则返回 false 。



示例 1:

输入: cards = [4, 1, 8, 7]
输出: true
解释: (8-4) * (7-1) = 24
示例 2:

输入: cards = [1, 2, 1, 2]
输出: false


提示:

cards.length == 4
1 <= cards[i] <= 9
"""
from typing import List

EPS = 1e-9
class Solution:


    def judgePoint24(self, cards: List[int]) -> bool:
        """
        四种运算有六种情况，
        每次计算前两个，然后把结果替换掉前两个，次数card的长度-1
        通过dfs
        :param cards:
        :return:
        """
        #如果只剩一位，说明当前即为结果
        len1 = len(cards)
        if len1==1:
            return abs(cards[0]-24) < EPS
        #遍历所有情况，递归
        for i,x in enumerate(cards):
            for j in range(i+1,len1):
                y = cards[j]
                #结果
                doList = [x+y,x-y,y-x,x * y]
                if x:
                    doList.append(y/x)
                if y:
                    doList.append(x/y)
                next = cards[:j] + cards[j+1:]
                for k in doList:
                    next[i] = k
                    if self.judgePoint24(next):
                        return True
        #遍历完了都没返回TRUE就说明已经是FALSE了
        return False
if __name__ == '__main__':
    print(Solution().judgePoint24([1,2,1,2]))